#include <bits/stdc++.h>
using namespace std;
/*
16. 最接近的三数之和
已解答
中等
相关标签
相关企业
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

 

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
示例 2：

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
 

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
*/

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
		int closeNum = nums[0] + nums[1] + nums[2];
		for (int i = 0; i < nums.size() - 2; ++i) {
			if (i > 0 && nums[i] == nums[i - 1])
				continue;
			int left = i + 1;
			int right = nums.size() - 1;
			while (left < right) {
				int cur = nums[i] + nums[left] + nums[right];
				if (abs(cur - target) < abs(closeNum - target)) {
					closeNum = cur;
				}
				// 指针移动
				if (cur < target) {
					++left;
				} else if (cur > target) {
					--right;
				} else {
					return cur;
				}
			}
		}
		return closeNum;
	}
};